/*
 * @Author: liusheng
 * @Date: 2022-04-26 17:50:54
 * @LastEditors: liusheng
 * @LastEditTime: 2022-04-26 18:23:07
 * @Description: 剑指 Offer II 045. 二叉树最底层最左边的值
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 
 剑指 Offer II 045. 二叉树最底层最左边的值
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

 

示例 1:

          1
         / \
        2   3

输入: root = [2,1,3]
输出: 1
示例 2:
          1
         / \
        2   3
       /   / \  
      4   5   6 
         /
        7

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
 

提示:

二叉树的节点个数的范围是 [1,104]
-231 <= Node.val <= 231 - 1 
 

注意：本题与主站 513 题相同： https://leetcode-cn.com/problems/find-bottom-left-tree-value/
 */

#include "header.h"
// Definition for a binary tree node.
struct TreeNode {
    int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode *> levelNodesQ;
        levelNodesQ.push(root);

        int bottomLeftV = 0;
        while (!levelNodesQ.empty())
        {
            int curLevelNodeNum = levelNodesQ.size();
            //keep the first value in every level
            bottomLeftV = levelNodesQ.front()->val;
            //process all this level node,then pop them all out
            //after for loop  keep the levelNodesQ only has nodes the next level
            for (int i = 0; i < curLevelNodeNum; ++i)
            {
                TreeNode * curNode = levelNodesQ.front();
                levelNodesQ.pop();

                if (curNode->left)
                {
                    levelNodesQ.push(curNode->left);
                }

                if (curNode->right)
                {
                    levelNodesQ.push(curNode->right);
                }
            }
        }

        return bottomLeftV;
    }
};

/*
recursive solution:keep the first value show up when level growth
*/
class Solution2 {
public:
    int findBottomLeftValue(TreeNode* root) {
        visitRecursive(root,0);
        return bottomLeftV;
    }
private:
    void visitRecursive(TreeNode * root,int level)
    {
        if (!root)
        {
            return;
        }

        //keep the first time level greater than current max level
        //so it's the most left value in the level
        if (level > maxLevel)
        {
            maxLevel = level;
            bottomLeftV = root->val;
        }

        visitRecursive(root->left,level + 1);
        visitRecursive(root->right,level + 1);
    }
private:
    int bottomLeftV;//keep the bottomLeft Value
    
    //keep the current max level,should init to -1 for the first time compare
    int maxLevel = -1;
};